#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2020 crane <crane@sharp>
#
# Distributed under terms of the MIT license.

"""

    定义/definitions:
        board: 整个棋盘和棋盘所有维护的状态
        chess_board: 整个棋盘

        grid: board中一个(3*3)的小棋盘
        grid_idx: 一个(row, col)坐标位于哪个小棋盘(对小棋盘从0开始编号)
        grid_width: 一个小棋盘的边长: 默认是3 (可以配置)

        top_width: 一个大棋盘的边长(等于小棋盘width的平方)

        slot: 棋盘中的一个坐标格子(row, col), 任何两个slot的坐标都不同.
        pos: 一个slot的坐标(row, col)
"""

import sys
import math
import copy
from pprint import pprint

import random
from collections import defaultdict


class Board:
    def __init__(self, grid_width=3):
        self.has_inited = False

        self.GridWidth = grid_width
        self.TopWidth = self.GridWidth ** 2

        self.total_ava_space = set( range(1, self.TopWidth+1) )

        self.total_num = self.TopWidth * self.TopWidth
        self.fixed_num = 0

        self.chess_board = self.make_board()

        self.row_occupied_nums  = defaultdict(set)      # row_num : occupiedilable__nums
        self.col_occupied_nums  = defaultdict(set)
        self.grid_occupied_nums = defaultdict(set)

        self.remain_pos = self.make_all_remain_pos()

        self.assert_loc_grid_test()

    def make_board(self):
        slot = 0
        one_row = [ copy.deepcopy(slot) for i in range(self.TopWidth)]
        matrix = [ copy.deepcopy(one_row) for i in range(self.TopWidth)]
        return matrix

    def make_all_remain_pos(self):
        s = set()
        for r in range(self.TopWidth):
            for c in range(self.TopWidth):
                s.add((r, c))

        return s

    def init_fixed(self, fixed_list):
        # support only called once: 只能调用一次
        if self.has_inited:
            raise Exception("inited")

        self.has_inited = True

        for row, col, value in fixed_list:
            self.set_slot(row-1, col-1, value)

    # 设置slot和其它相应"状态"
    def set_slot(self, row, col, value):
        if value > self.TopWidth or value < 1:
            raise Exception("fail set_slot value", value)

        grid_idx = self.loc_grid_idx(row,col)
        self.chess_board[row][col] = value

        if value in self.row_occupied_nums[row]:
            raise Exception("row [%s] already has value [%s]" % (row, value))

        if value in self.col_occupied_nums[col]:
            print(self.col_occupied_nums[col], (row, col) , value)
            raise Exception("col [%s] already has value [%s]" % (col, value))

        if value in self.grid_occupied_nums[grid_idx]:
            raise Exception("grid [%s] already has value [%s]" % (grid_idx, value))

        self.row_occupied_nums[row].add(value)
        self.col_occupied_nums[col].add(value)
        self.grid_occupied_nums[grid_idx].add(value)

        self.remain_pos.remove((row, col))            # 把这个位置设置为已经解决
        self.fixed_num += 1

    # 清除slot和其它相应"状态"
    def clear_slot(self, row, col, value):
        self.chess_board[row][col] = 0

        grid_idx = self.loc_grid_idx(row,col)

        self.row_occupied_nums[row].remove(value)
        self.col_occupied_nums[col].remove(value)
        self.grid_occupied_nums[grid_idx].remove(value)

        self.remain_pos.add( (row, col) )
        self.fixed_num -= 1



    # ------------------- assert ---------------------
    def assert_loc_grid_test(self):
        if self.GridWidth == 3:
            assert self.loc_grid_idx(0,0) == 0
            assert self.loc_grid_idx(2,2) == 0

            assert self.loc_grid_idx(3,3) == 4
            assert self.loc_grid_idx(5,5) == 4

            assert self.loc_grid_idx(6,6) == 8
            assert self.loc_grid_idx(8,8) == 8

        if self.GridWidth == 2:
            assert self.loc_grid_idx(0,0) == 0
            assert self.loc_grid_idx(1,1) == 0

            assert self.loc_grid_idx(2,2) == 1
            assert self.loc_grid_idx(3,3) == 1


        print("asert loc_grid_idx() ok!")

    # 计算这个坐标在哪个sub_grid(小棋盘)中
    def loc_grid_idx(self, row, col):
        # return row // self.GridWidth * (self.TopWidth / self.GridWidth) + col // self.GridWidth
        return row // self.GridWidth * self.GridWidth + col // self.GridWidth

    def show_board(self):
        # 把棋盘结果分块输出
        digit_len = len(str(self.TopWidth))
        print()

        for row in range(self.TopWidth):
            for col in range(self.TopWidth):
                fmt_s = "%" + str(digit_len) + "s,"
                print(fmt_s % self.chess_board[row][col], sep=',', end='')
                if (col + 1) % self.GridWidth == 0:
                    print('|', end='')

            print()
            if (row + 1) % self.GridWidth == 0:
                print('_' * (self.TopWidth * 2) * digit_len)

        print()

    def assert_every_where(self):
        for i in range(self.TopWidth):

            assert len(self.row_occupied_nums[i]) == self.TopWidth
            assert len(self.col_occupied_nums[i]) == self.TopWidth
            assert len(self.grid_occupied_nums[i]) == self.TopWidth

            for num in range(1, self.TopWidth+1):
                assert num in self.row_occupied_nums[i]
                assert num in self.col_occupied_nums[i]
                assert num in self.grid_occupied_nums[i]

        print("assert_every_where passed!")

    def run(self):
        # 递归深度和未解决的slot个数相关
        sys.setrecursionlimit(len(self.remain_pos) + 100)

        if self.unfixed_num == 0:
            print("Maybe you have inited all slots, Has no unfixed slots!")
            return

        self.solve_order = []
        self.try_cnt = 0

        has_solution = self.recursive_try()
        print("solve_order>", self.solve_order)
        print("\ntryed count ", self.try_cnt)

        if has_solution:
            self.assert_every_where()

        return has_solution

    def recursive_try(self):
        if self.is_end:
            return True

        self.try_cnt_plus()
        cur_try_pos, cur_try_occupy_nums,  _ = self.min_price_pos

        # cur_slot_availa_nums = self.difference(cur_try_occupy_nums)         # 按固定顺序遍历
        cur_slot_availa_nums = self.shuffled_difference(cur_try_occupy_nums)  # 打乱顺序, 随机处理(可能会更快)

        for cad_num in cur_slot_availa_nums:
            self.set_slot(*cur_try_pos, cad_num)

            if self.recursive_try():
                self.solve_order.insert(0, cur_try_pos)
                return True
            else:
                self.clear_slot(*cur_try_pos, cad_num)

        return False

    def try_cnt_plus(self):
        self.try_cnt += 1
        output_cnt = 10000 * 100     # 10w

        if self.try_cnt % output_cnt == 0:
            print("processing try_cnt", self.try_cnt)

    # def slot_availa_nums(self, row, col, grid_idx):
    #     total_occuiped_set = self.occupied_nums(row, col)

    #     slot_ava_nums = self.total_ava_space.difference(total_occuiped_set)
    #     return slot_ava_nums

    #     l = list(slot_ava_nums)
    #     random.shuffle(l)
    #     return l

    def shuffled_difference(self, slot_occupied):
        slot_ava_nums = self.total_ava_space.difference(slot_occupied)

        l = list(slot_ava_nums)
        random.shuffle(l)
        return l

    def difference(self, slot_occupied):
        slot_ava_nums = self.total_ava_space.difference(slot_occupied)
        return slot_ava_nums

    def occupied_nums(self, row, col):
        # 计算坐标(row, col)中 "不可选"的数字: 这些数字是被本行, 本列, 当前grid_idx占了的nums!
        grid_idx = self.loc_grid_idx(row, col)

        ts = self.row_occupied_nums[row].union(self.col_occupied_nums[col], self.grid_occupied_nums[grid_idx])
        return ts

    @property
    def min_price_pos(self):
        # 从未解决的slot中选取最容易解决的: 解空间(可选数字)最少的
        best_try_pos = (None, None)
        max_occupy_cnt = -1

        ret_occupy_set = set()

        assert self.remain_pos
        for cadidate_pos in self.remain_pos:
            cadidate_occupy_set = self.occupied_nums(*cadidate_pos)
            cadidate_occupy_cnt = len(cadidate_occupy_set)

            if cadidate_occupy_cnt > max_occupy_cnt:
                max_occupy_cnt = cadidate_occupy_cnt
                ret_occupy_set = cadidate_occupy_set
                best_try_pos = cadidate_pos

        return best_try_pos, ret_occupy_set, max_occupy_cnt

    @property
    def is_end(self):
        # 判断是否所有unsolved都解决了
        return self.unfixed_num == 0

    @property
    def unfixed_num(self):
        # 计算未解决的slot数量
        return self.total_num - self.fixed_num


def file_fixed_slots(file_name=""):
    if file_name == "":
        file_name = "./lst.txt"

    lst = []

    with open(file_name) as file:
        for line in file:
            line = line.strip()
            if line == '':
                continue

            # 支持注释
            if line.startswith("#"):
                print(line)
                continue

            nums = list(map(int, line.split(' ')))
            lst.append(nums)

    return lst

def simplest_fixed_slot(grid_width):
    fixed_slots = [ ]
    jump_steps = grid_width * (grid_width-1)

    for i in range(grid_width):
        for j in range(grid_width):

            num = i * grid_width + j +1
            fixed_slots.append( (i+1, j+1, num) )

            # pair_num = num                       # 左上角grid和右下角grid保持相同
            pair_num = grid_width ** 2 - num + 1 # 左上角grid和右下角grid保持互补
            pair_row = i + jump_steps + 1
            pair_col = j + jump_steps + 1

            fixed_slots.append( (pair_row, pair_col, pair_num) )

    return fixed_slots


class Solution:
    def __init__(self, grid_width=3):
        board = Board(grid_width)

        board.init_fixed (
            # file_fixed_slots("./lst_world_difficult.txt")
            # file_fixed_slots()
            simplest_fixed_slot(grid_width)
        )

        # NOTE: 如果不做init(), 就相当于随机生成整个数独board
        has_solution = board.run()
        board.show_board()
        if has_solution:
            print("\n!Got one perfect solution for sudo game!")


def test():
    s = Solution(grid_width=3)

def main():
    test()

if __name__ == "__main__":
    main()
